#include "HeapSort.h"

HeapSort::HeapSort(void)
{
}

HeapSort::~HeapSort(void)
{
}

void HeapSort::doHeapSort(vector<int> &A)
{
	this->heapSize = A.size();

	this->doBuildMaxHeap(A);

	for(int i=this->heapSize; i >= 2; i--)
	{
		this->doSwap(A, 0, i-1);
		this->heapSize--;
		this->doMaxHeapify(A, 1);
	}

}

void HeapSort::doBuildMaxHeap(vector<int> &A)
{
	for(int i=(int)floor((double)this->heapSize/2); i>=1; i--) 
	{
		this->doMaxHeapify(A, i);
	}
}

void HeapSort::doMaxHeapify(vector<int> &A, int i)
{
	int L, R;
	int largest = i;

	L = this->getChildIndex(i);
	R = L + 1;

	if(L <= this->heapSize && A[L-1] > A[i-1])
		largest = L;
	if(R <= this->heapSize && A[R-1] > A[largest-1])
		largest = R;

	if(largest != i)
	{
		this->doSwap(A, largest-1, i-1);
		this->doMaxHeapify(A, largest);
	}
}

int HeapSort::getChildIndex(int i)
{
	int log2value = (int)floor(log((double)i)/log(2.0));
	
	return (int)(pow(2.0, log2value+1)+2*(i-pow(2.0, log2value)));
}

void HeapSort::doSwap(vector<int> &A, int up, int down)
{
	int tmp = A[down];
	A[down] = A[up];
	A[up] = tmp;
}